The present invention relates to computer systems and more particularly to managing memory for a run-time environment.
A dynamic run-time environment for a language such as JAVA(trademark) is responsible for managing memory for objects that are created and destroyed during the execution of a program. An object may be defined as a logically contiguous atomic unit of typed state of the program. Objects thus encapsulate data in particular regions of memory that are allocated and deallocated for the program by the dynamic run-time environment.
The state of the program, or xe2x80x9cprogram state,xe2x80x9d is the set of objects, the content of the objects, and the references between the objects that exist at a specific point in time during the execution of the program. A xe2x80x9creferencexe2x80x9d to an object is an entity used to identify and ultimately access a region of memory that stores the data of the object. Typically, references between objects in a run-time environment are encoded using machine pointers. A machine pointer is a native entity that contains the address of the object in the main memory, which can be a real address or, more commonly, a virtual address. Since machine pointers are closely coupled to the underlying hardware and firmware of a computer system, machine pointers provide a fast means of accessing objects and, hence, are a popular implementation for references.
In a run-time environment, however, a program state that contains machine pointers is so machine-dependent that it is sometimes disadvantageous. For example, it may be desirable to store the program state on disk or other secondary storage medium and restore the stored program state to main memory. Some run-time environments, in fact, are designed to use the same program state on different types of machines. For instance, such run-time environments provide load-balancing and crash recovery functions by transferring the execution of a program (including its state) from one machine to another.
One of the reasons why machine pointers are not machine-independent is that the size in bits of a machine pointer is determined by the extent of the virtual address space, which varies between computer architectures. In fact, some computer architectures even have pointers of varying sizes, for example, near (16-bit) pointers and far (32-bit) pointers. If program state includes machine pointers whose size varies from platform to platform, then the size of objects will vary from platform to platform. Furthermore, since the size of intervening objects will vary, the relative locations between objects will vary from platform to platform. For example, on a platform with near pointer the relative location of one object can be 48 bytes from another object, but on a platform with far pointers, the relative location might increase to 96 bytes.
One approach directed to machine independence, known as xe2x80x9cpointer swizzling,xe2x80x9d employs two completely different formats for representing references: a machine-dependent runtime format using pointers for references in main memory, and a platform invariant format for encoding references in secondary storage. When the reference is written to secondary storage, machine pointers are converted into a machine-independent symbol such as a string or serial number. When the reference is read back into main memory from secondary storage, the symbol is unswizzled and converted back into a machine pointer. Swizzling is also referred to as xe2x80x9cserializationxe2x80x9d and xe2x80x9cpickling.xe2x80x9d Since the size and relative locations of objects differs between platforms, swizzling and unswizzling operations employ a look-up technique into an associative data structure, wherein a machine pointer is associated with a corresponding symbol. Look-up operations, however, are computationally expensive, requiring many memory accesses into an auxiliary symbol table, typically implemented by a hash table or binary tree stored in memory. Thus, frequent storage and retrieval of program state into and out of secondary storage can be responsible for a significant drain on system performance.
Differences between server environments make machine independence very difficult to achieve for portable run-time environments even with pointer swizzling. For example, some operating systems, in practice if not by design, limit the guaranteed size of contiguous virtual memory to a xe2x80x9cpage,xe2x80x9d typically about two or four kilobytes in size. This page-size limitation is particularly common for allocating objects in shared memory for access by different processes. Consequently, in paged memory systems, large objects such as arrays cannot be contiguously allocated for these servers. Prior paged memory systems either failed when sufficiently large blocks of virtual memory were not available, or employed ad hoc constructions to simulate specific array types.
Failure to allocate memory for large objects, merely because sufficient contiguous virtual address space is unavailable, limits the availability and marketability for such run-time environments. Ad hoc simulations, moreover, are impracticable for paged memory servers especially for large, user defined objects, because they are unknown to the designer of the run-time environment. Furthermore, it is difficult to integrate such ad hoc solutions with the pointer swizzling operations for addressing machine independence.
There exists a need for a memory management system that can efficiently save and restore program state in a machine-independent format. Specifically, a need exists for a reference format that can be easily stored and has comparatively efficient run-time performance. There is also a need for a memory management system that is portable to, and capable of working with, operating systems that impose a page-size limitation to contiguous memory.
These and other needs are addressed by the present invention, in which a genus of machine-independent formats, called a numeric reference format, is defined for both run-time and storage. A numeric reference to an object encodes the location of the object as an integral offset from an implicit machine pointer. Since the semantics of an integer, as opposed to a native machine pointer, can be completely specified in terms of size and byte-order, integers can be easily translated between machines without applying computationally expensive pointer swizzling operations.
Accordingly, one aspect of the invention relates to a computer-implemented method and a computer-readable medium bearing instructions for managing memory for a run-time environment. The methodology includes storing a plurality of objects in a virtual memory; storing references between the objects as numeric references in the virtual memory; and storing the objects in a secondary storage that is not part of the virtual memory and the references in a numeric reference format in a secondary storage that is not part of the virtual memory.
Another aspect of the invention involves a computer-implemented method and a computer-readable medium bearing instructions for managing memory for a run-time environment. Management of the run-time environment involves loading objects into virtual memory from secondary storage that is not part of the virtual memory; loading references between the objects as numeric references into the virtual memory; and dereferencing one of the numeric references by adding, to a machine pointer, an offset contained within the numeric reference. Use of numeric references for storing references between objects provides an invariant representation for references, thereby enabling machine-independent program state to be stored within and loaded from secondary storage that is not part of the virtual memory.
In circumstances where program state containing the objects and references is to be used in environments where the size of contiguous virtual memory segments is limited, the objects are stored or loaded into virtual memory in a number of fixed-size contiguous chunks called xe2x80x9cpages.xe2x80x9d A xe2x80x9cpage-offsetxe2x80x9d numeric reference for such environments includes a page number, which is used to index a page map that contains a page pointer to the beginning of the page, and an offset. Page-offset numeric references are dereferenced by adding the offset in the numeric reference to the page pointer obtained from the page map based on the page number in the numeric reference. Use of page-offset numeric references allows for a software virtual memory system to be systematically implemented for all system-defined and user-defined types supported in a run-time environment, in effect, implementing a software paged memory system.
Still other objects and advantages of the present invention will become readily apparent from the following detailed description, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.